package com.algorithm.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HandReverse {
    public static void main(String[] args) {
        String str = "abcdefg";
        //翻转字符串
        char[] chars = str.toCharArray();
        reverseLeftRotate(chars, 0, str.length() - 1, 3);
        System.out.println(Arrays.toString(chars));
        // 翻转句子
        reverseSentence(" hello world! reverse words!");
    }

    public static void reverseSentence(String str) {
        if (!str.endsWith(" ")){
            str +=" ";
        }
        char[] charArray = str.toCharArray();
        Integer[] spaces = findSpace(charArray);

        Integer[] words = new Integer[spaces.length];

        for (int i = 0; i < spaces.length; i++) {
            int wordIndex;
            if (i == 0) {
                wordIndex = spaces[0] +1;
            } else {
                wordIndex = spaces[i] - spaces[i - 1];
            }
            words[i] = wordIndex;
        }

        int end = str.length() - 1;
        for (int i = 0; i < spaces.length; i++) {
            int wordIndex = words[i];
            reverseLeftRotate(charArray, 0, end, wordIndex - 1);
            //System.out.println(String.valueOf(charArray) + "\t 0--" + end);
            end -= wordIndex;
        }

        System.out.println(String.valueOf(charArray));
    }


    private static Integer[] findSpace(char[] str) {
        List<Integer> list = new ArrayList<>();
        char[] charArray = str;
        for (int i = 0; i < charArray.length; i++) {
            if (charArray[i] == ' ') {
                list.add(i);
            }
        }
        return list.toArray(new Integer[list.size()]);
    }


    /**
     * @param str   :
     * @param end   :
     * @param point :
     * @author : daniel.yang
     * @date : 2018/11/7
     * @desc : 从0开始数到point位置进行翻转,字符串为str截取从开始到end
     */
    public static void reverseLeftRotate(char[] str, int start, int end, int point) {
        reverse(str, start, point);
        reverse(str, point + 1, end);
        reverse(str, start, end);
    }


    public static void reverse(char[] str, int from, int to) {
        while (from < to) {
            char t = str[from];
            str[from++] = str[to];
            str[to--] = t;
        }
    }
}
